import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-09-11
 * Time: 16:26
 */
public class MyHeap {
    //初始数组容量为10
    public int[] array = new int[10];
    //数组有效元素个数
    public int size;
    //给定一个带参数初始化的构造方法
    public MyHeap(int[] array) {
        this.array = array;
        this.size = array.length;
    }
    public MyHeap() {

    }

    //向下调整_建小根堆
    public void siftDownToMinHeap(int parent) {
        int child = 2*parent + 1;

        while (child < this.size) {
            //若右孩子存在,比较左右孩子的大小
            if (child + 1 < this.size && this.array[child + 1] < this.array[child]) {
                child = child + 1;
            }

            //如果child比parent的值还小，那么交换，符合小根堆
            if (this.array[child] < this.array[parent]) {
                swap(this.array,child,parent);
                //parent继续向下走，防止这次交换后破坏堆结构
                parent = child;
                child = 2*parent + 1;
            }else {
                //符合堆结构就跳出循环，避免不必要的循环
                break;
            }
        }
    }

    //交换两个数
    private void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //创建小根堆
    public void createMinHeap() {
        //最后一个叶子结点的下标
        int child = this.size-1;
        //当parent == 0时，说明parent走到了树的根结点
        for(int parent = (child - 1)/2; parent >= 0; parent--) {
            //对每个非叶子结点进行向下调整
            siftDownToMinHeap(parent);
        }
    }

    //创建大根堆
    public void createMaxHeap() {
        //最后一个叶子结点的下标
        int child = this.size-1;
        //当parent == 0时，说明parent走到了树的根结点
        for(int parent = (child - 1)/2; parent >= 0; parent--) {
            //对每个非叶子结点进行向下调整
            siftDownToMaxHeap(parent);
        }
    }

    //向下调整_建大根堆
    public void siftDownToMaxHeap(int parent) {
        int child = 2*parent + 1;

        while (child < this.size) {
            //若右孩子存在,比较左右孩子的大小
            if (child + 1 < this.size && this.array[child + 1] > this.array[child]) {
                child = child + 1;
            }

            //如果child比parent的值还大，那么交换，符合大根堆
            if (this.array[child] > this.array[parent]) {
                swap(this.array,child,parent);
                //parent继续向下走，防止这次交换后破坏堆结构
                parent = child;
                child = 2*parent + 1;
            }else {
                //符合堆结构就跳出循环，避免不必要的循环
                break;
            }
        }
    }



    //向上调整_建立小根堆
    public void siftUpMinHeap(int key) {
        //判断数组满了没,满了进行扩容
        if (this.size == this.array.length) {
            this.array = Arrays.copyOf(array,2*array.length);
        }
        //将元素插入末尾
        array[this.size] = key;
        //此时插入元素的下标，即此时最后一个孩子的下标
        int child = this.size;
        siftUpToMin(child);
        this.size++;
    }
    //向上调整的逻辑部分
    public void siftUpToMin(int child) {
        //找到它的双亲结点
        int parent = (child - 1)/2;

        //开始向上调整
        while (child > 0) {
            if (array[parent] > array[child]) {
                //如果双亲结点的值大于孩子结点的值，那么交换，孩子结点往上调
                swap(array,child,parent);

                //交换完成后，继续向上调整，防止树还未符合堆的性质
                child = parent;
                parent = (child - 1)/2;
            }else {
                //如果此时检测到树已经符合堆的性质了，就退出循环
                break;
            }
        }
    }

    //向上调整_建立大根堆
    public void siftUpMaxHeap(int key) {
        //判断数组满了没,满了进行扩容
        if (this.size == this.array.length) {
            this.array = Arrays.copyOf(array,2*array.length);
        }
        //将元素插入末尾
        array[this.size] = key;
        //此时插入元素的下标，即此时最后一个孩子的下标
        int child = this.size;
        siftUpToMax(child);
        this.size++;
    }
    //向上调整的逻辑部分
    public void siftUpToMax(int child) {
        //找到它的双亲结点
        int parent = (child - 1)/2;

        //开始向上调整
        while (child > 0) {
            if (array[parent] < array[child]) {
                //如果双亲结点的值大于孩子结点的值，那么交换，孩子结点往上调
                swap(array,child,parent);

                //交换完成后，继续向上调整，防止树还未符合堆的性质
                child = parent;
                parent = (child - 1)/2;
            }else {
                //如果此时检测到树已经符合堆的性质了，就退出循环
                break;
            }
        }
    }

    //删除_维护小根堆
    public int pollToMinHeap() {
        int val = this.array[0];
        swap(this.array,0,this.size-1);
        this.size--;
        siftDownToMinHeap(0);
        //返回被删除元素
        return val;
    }

    //删除_维护大根堆
    public int pollToMaxHeap() {
        int val = this.array[0];
        swap(this.array,0,this.size-1);
        this.size--;
        siftDownToMaxHeap(0);
        //返回被删除元素
        return val;
    }

    //升序排序
    public int[] heapSortRise() {
        //建大根堆
        createMaxHeap();

        //进行排序操作
        while (this.size > 1) {
            //交换堆顶元素和堆尾元素
            swap(this.array,0,this.size - 1);
            //缩小范围
            this.size--;
            //从根结点开始对新的堆进行调整
            siftDownToMaxHeap(0);
        }

        return this.array;
    }
}
